from general_utilities import *
from map import *
from entities import *
import random
import time

# First an implementation of A* for use in finding the way from one tile to another in the same tile

import _heapq
import math
        
class Astar_node:
  def __init__(self,path_to):
    self.path_to = path_to # [(down,right)]
    self.moves_to = len(path_to)

class Node_to_process:
  def __init__(self,moves_to,moves_from,down_right):
    self.moves_to = moves_to    
    self.moves_from = moves_from
    self.heuristic = self.moves_from + self.moves_to
    self.down = down_right[0]
    self.right = down_right[1]
    
  def __cmp__(self,other):
    if self.heuristic == other.heuristic:
      return 0
    elif self.heuristic > other.heuristic:
      return 1
    else:
      return -1

def straight_line_distance(down_right_1,down_right_2):
  return math.sqrt(pow(down_right_1[0]-down_right_2[0],2) + pow(down_right_1[1]-down_right_2[1],2))
    
def astar_pathfind_withinroom(d,from_pos,to_pos,exclude_pos,water_ok,max_range=1e6):
  # return a [(down,right)], including to_pos but not from_pos (or None)
  # NOW CHANGED - return the above, and a flag indicating whether the way was blocked
  # exclude_pos is a list of disallowed Pos - might be entities, etc
  if not from_pos.same_room(to_pos):
    return None,0
  if to_pos.down==from_pos.down and to_pos.right==from_pos.right:
    return [],0
  if to_pos in exclude_pos:
    return None,1
  if len(exclude_pos)==0:
    from_dict = d.l.known_routes.get(from_pos.to_tuple(),None)
    if from_dict is not None:
      to_routes = from_dict.get(to_pos.to_tuple(),None)
      if to_routes is not None:
        to_route_for_this_movement_type = to_routes.get(water_ok,None)
        if to_route_for_this_movement_type is not None:
          #print "using a stored path",to_route_for_this_movement_type
          return to_route_for_this_movement_type,0
  #print "call to astar_pathfind_withinroom, from ",from_pos," to ",to_pos, " with ",len(exclude_pos)," excluded"
  result = []
  room = d.l.room_at(from_pos)
  room_info = {} # keyed by (down,right), value is Astar_node
  room_info[(from_pos.down,from_pos.right)] = Astar_node([])
  open_nodes = [] # heapq of Node_to_process
  _heapq.heappush(open_nodes, Node_to_process(0,straight_line_distance((from_pos.down,from_pos.right),(to_pos.down,to_pos.right)),(from_pos.down,from_pos.right)))
  exclude = {} # keyed by (down,right), value is 1 or key is missing
  for pos in exclude_pos:
      exclude[(pos.down,pos.right)] = 1
  walkable = {} # keyed by (down,right), value is switch or key is missing
  destination_reached = 0
  obstruction = 0
  count = 0
  count2 = 0
  while (not destination_reached and not len(open_nodes)==0):
    next_node = _heapq.heappop(open_nodes)
    for loc in d.shells[1]:
        try_loc = (next_node.down+loc[0],next_node.right+loc[1])
        count = count + 1          
        if try_loc[0]<0 or try_loc[0]>=room.height or try_loc[1]<0 or try_loc[1]>=room.width:
          continue
        if walkable.get(try_loc,1)==0:
          continue 
        elif not(try_loc in walkable):
          walkable[try_loc] = room.tiles[try_loc[0]][try_loc[1]].info().walkable_test_for_pathfinding(water_ok)
          if walkable[try_loc]==0:
            continue
        if abs(loc[0])+abs(loc[1])==2:
          # this is a diagonal move
          step_length = 1.5
        else:
          # this is an orthogonal move
          step_length = 1.0
        if (next_node.moves_to+step_length)>max_range:
          continue
        add = 0
        if try_loc in room_info:
          if (next_node.moves_to+step_length) < room_info[try_loc].moves_to:
            add = 1          
        else:
          if exclude.get(try_loc,0)==0:
            add = 1
          else:
            obstruction = 1
        if add:
          room_info[try_loc] = Astar_node(room_info[(next_node.down,next_node.right)].path_to+[try_loc])
          if try_loc[0]==to_pos.down and try_loc[1]==to_pos.right:
            destination_reached = 1
            break
          else:
            count2 = count2 + 1
            _heapq.heappush(open_nodes, Node_to_process(next_node.moves_to+step_length,straight_line_distance(try_loc,(to_pos.down,to_pos.right)),try_loc))
  if not destination_reached:
    return None,obstruction
  else:
    #print "considered ",count," pushed ",count2," and succeeded"
    path = room_info[(to_pos.down,to_pos.right)].path_to
    if len(exclude_pos)==0:
      #if d.l.known_routes.get(from_pos.to_tuple(),None) is None:
      #  d.l.known_routes[from_pos.to_tuple()] = {}
      #if d.l.known_routes[from_pos.to_tuple()].get(to_pos.to_tuple(),None) is None:
      #  d.l.known_routes[from_pos.to_tuple()][to_pos.to_tuple()] = path
      for i in range(len(path)-1):
        if i==0:
          this_from_pos = from_pos.to_tuple()
        else:
          this_from_pos = (from_pos.level,from_pos.r_down,from_pos.r_right,path[i-1][0],path[i-1][1])
        for j in range(i+1,len(path)):
          if j==len(path)-1:
            this_to_pos = to_pos.to_tuple()
          else:
            this_to_pos = (from_pos.level,from_pos.r_down,from_pos.r_right,path[j-1][0],path[j-1][1])
          if d.l.known_routes.get(this_from_pos,None) is None:
            d.l.known_routes[this_from_pos] = {}
          if d.l.known_routes[this_from_pos].get(this_to_pos,None) is None:
            d.l.known_routes[this_from_pos][this_to_pos] = {}
          d.l.known_routes[this_from_pos][this_to_pos][water_ok] = path[i:(j+1)]
    return path,obstruction

# Now info for navigating between rooms

RN_DIR_UP = 20
RN_DIR_DOWN = 21
RN_DIR_OUT = 22
RN_DIR_MONSTER_OUT = 23

class Room_network_node:
  # used by Room_network; one of these per room
  # with for_keys=1, exclude water routes but allow locked doors
  def __init__(self,d,room,for_keys=0):  
    self.exits = {DIR_UP:room.door_up>0, DIR_DOWN:room.door_down>0, DIR_RIGHT:room.door_right>0, DIR_LEFT:room.door_left>0, RN_DIR_UP:room.stairs_up_pos is not None, RN_DIR_DOWN:room.stairs_down_pos is not None, RN_DIR_OUT:room.exit_pos is not None, RN_DIR_MONSTER_OUT:room.monster_exit_pos is not None}
    self.exits_pos = {} # key is DIR or RN_DIR, value is Pos
    self.exits_to = {}  # key is DIR or RN_DIR, value is Pos
    self.exits_to_node = {} # key is DIR_ or RN_DIR_, value is (level, r_down, r_right, and a DIR or RN_DIR)
    if self.exits[RN_DIR_UP]:
      self.exits_pos[RN_DIR_UP] = room.stairs_up_pos
      self.exits_to[RN_DIR_UP] = d.l.tile_at(self.exits_pos[RN_DIR_UP]).to_pos
      self.exits_to_node[RN_DIR_UP] = (self.exits_to[RN_DIR_UP].level, self.exits_to[RN_DIR_UP].r_down, self.exits_to[RN_DIR_UP].r_right, RN_DIR_DOWN)
    if self.exits[RN_DIR_DOWN]:
      self.exits_pos[RN_DIR_DOWN] = room.stairs_down_pos
      self.exits_to[RN_DIR_DOWN] = d.l.tile_at(self.exits_pos[RN_DIR_DOWN]).to_pos
      self.exits_to_node[RN_DIR_DOWN] = (self.exits_to[RN_DIR_DOWN].level, self.exits_to[RN_DIR_DOWN].r_down, self.exits_to[RN_DIR_DOWN].r_right, RN_DIR_UP)
    if self.exits[RN_DIR_OUT]:
      self.exits_pos[RN_DIR_OUT] = room.exit_pos
      self.exits_to[RN_DIR_OUT] = None
      self.exits_to_node[RN_DIR_OUT] = None
    if self.exits[RN_DIR_MONSTER_OUT]:
      self.exits_pos[RN_DIR_MONSTER_OUT] = room.monster_exit_pos
      self.exits_to[RN_DIR_MONSTER_OUT] = None
      self.exits_to_node[RN_DIR_MONSTER_OUT] = None
    for dir in (DIR_DOWN, DIR_UP, DIR_RIGHT, DIR_LEFT):
      if self.exits.get(dir,0):
        self.exits_pos[dir] = room.get_mid_wall(dir)
        if d.l.tile_at(self.exits_pos[dir]).info().can_be_unlocked and not for_keys:
          self.exits[dir] = 0 # locked door, not a part of the network
          continue
        self.exits_to[dir] = d.l.tile_at(self.exits_pos[dir]).to_pos   
        self.exits_to_node[dir] = (self.exits_to[dir].level, self.exits_to[dir].r_down, self.exits_to[dir].r_right, opposite(dir))
    self.exits_to_room = {} # key is DIR or RN_DIR, value is (level,r_down,r_right)
    for dir in (DIR_DOWN, DIR_UP, DIR_RIGHT, DIR_LEFT, RN_DIR_UP, RN_DIR_DOWN, RN_DIR_OUT, RN_DIR_MONSTER_OUT):
      if self.exits[dir]:
        if self.exits_to[dir] is not None:
          self.exits_to_room[dir] = (self.exits_to[dir].level,self.exits_to[dir].r_down,self.exits_to[dir].r_right)         
        else:
          self.exits_to_room[dir] = None
    self.routes = {} # First key is a DIR_ code or one of the RN_DIR_ codes above, second key ditto. If no route, then no entry in dict, or value is None. Otherwise, value is length of route.
    self.water_routes = {} # First key is a DIR_ code or one of the RN_DIR_ codes above, second key ditto. If no route, then no entry in dict, or value is None. Otherwise, value is length of route.
    route_is_dry = {} # Same keys as above. For optimisation.
    for dir1 in self.exits.keys():
      self.water_routes[dir1] = {}
      route_is_dry[dir1] = {}
      if self.exits[dir1]:
        pos1 = self.exits_pos[dir1] 
        for dir2 in self.exits.keys():
          if self.exits[dir2]:
            if dir1 <> dir2:
              if dir2 in self.water_routes:
                if dir1 in self.water_routes[dir2]:
                  self.water_routes[dir1][dir2] = self.water_routes[dir2][dir1]
                  continue
              pos2 = self.exits_pos[dir2] 
              path,junk = astar_pathfind_withinroom(d,pos1,pos2,[],1)
              if path is None:
                self.water_routes[dir1][dir2] = None
              else:
                self.water_routes[dir1][dir2] = len(path)
                route_is_dry[dir1][dir2] = 1 # now check; do we get our feet wet? If not, don't need a non-watery path
                this_pos = Pos(room.level,room.r_down,room.r_right,0,0)
                for step in path: 
                  this_pos.right = step[1]
                  this_pos.down = step[0]
                  if d.l.tile_at(this_pos).info().is_watery:
                    route_is_dry[dir1][dir2] = 0
                    break
    for dir1 in self.exits.keys():
      self.routes[dir1] = {}
      if self.exits[dir1]:
        pos1 = self.exits_pos[dir1] 
        for dir2 in self.exits.keys():
          if self.exits[dir2]:
            if dir1 <> dir2:
              if dir2 in self.routes:
                if dir1 in self.routes[dir2]:
                  self.routes[dir1][dir2] = self.routes[dir2][dir1]
                  continue
              if dir1 in self.water_routes:
                if dir2 in self.water_routes[dir1]:
                  if self.water_routes[dir1][dir2] is not None:
                    if route_is_dry[dir1][dir2]:
                      self.routes[dir1][dir2] = self.water_routes[dir1][dir2]
                      continue
                    pos2 = self.exits_pos[dir2] 
                    path,junk = astar_pathfind_withinroom(d,pos1,pos2,[],0)
                    if path is None:
                      self.routes[dir1][dir2] = None
                    else:
                      self.routes[dir1][dir2] = len(path) 
                    continue
              self.routes[dir1][dir2] = None # no wet route, so there will be none dry
       
  
class Room_network:
  # includes info about how quick it is to get from one room-exit to another
  def __init__(self,d,for_keys=1):
    self.nodes = {} # key is (level, r_down, r_right), value is a Room_network_node
    self.for_keys = for_keys
    # We'll now do this computation 'as needed'
    #for level in d.l.levels:
    #  for r_i in range(level.r_height):
    #    for r_j in range(level.r_width):
    #      room = level.rooms[r_i][r_j]
    #      self.nodes[(level.level,r_i,r_j)] = Room_network_node(d,room)
  
  def get_node(self,d,key):
    # key is (level, r_down, r_right), value is a Room_network_node
    if key in self.nodes and self.nodes[key] is not None:
      return self.nodes[key]
    else:
      level = key[0]
      r_down = key[1]
      r_right = key[2]
      room = d.l.levels[level].rooms[r_down][r_right]
      self.nodes[key] = Room_network_node(d,room,self.for_keys)
      return self.nodes[key]
    
  def __str__(self):  
    result = ""
    for key in self.nodes.keys():
      result = result + "*** " + str(key) + "***\n" + str(self.nodes[key].routes) + "\n\n" 
    return result

class Astar_roomnode:
  def __init__(self,path_to,moves_to):
    self.path_to = path_to # [(level, r_down, r_right, dir)]
    self.moves_to = moves_to

class Roomnode_to_process:
  def __init__(self,moves_to,moves_from,node):
    self.moves_to = moves_to    
    self.moves_from = moves_from
    self.heuristic = self.moves_from + self.moves_to
    self.level = node[0]
    self.r_down = node[1]
    self.r_right = node[2]
    self.dir = node[3]
    
  def __cmp__(self,other):
    if self.heuristic == other.heuristic:
      return 0
    elif self.heuristic > other.heuristic:
      return 1
    else:
      return -1

def straight_line_long_distance(node_1,node_2):
  if node_1[0] <> node_2[0]:
    return 200*abs(node_1[0] - node_2[0])
  elif node_1[1]<>node_2[1] or node_1[2]<>node_2[2]:
    return 20*math.sqrt(pow(node_1[1]-node_2[1],2) + pow(node_1[2]-node_2[2],2))
  else:
    return 10

def astar_pathfind_betweenrooms(d,entity,from_node,to_node):
  # return a [(level, r_down, r_right, dir)], including from_node but not to_node (or None)
  # input nodes are also (level, r_down, r_right, dir)
  # characters get restricted info on portals, hence the is_character flag argument
  # print "nav from ",from_node," to ",to_node
  #
  # Now only use this for rooms on the same floor
  #
  #if from_node[0] < to_node[0]:
    ## need to go downstairs first
    #stairs_down_pos = d.l.levels[from_node[0]].stairs_down_pos
    #lower_stairs_up_pos = d.l.tile_at(stairs_down_pos).to_pos
    #stairs_down = (from_node[0],stairs_down_pos.r_down,stairs_down_pos.r_right,RN_DIR_DOWN)
    #lower_stairs_up = (lower_stairs_up_pos.level,lower_stairs_up_pos.r_down,lower_stairs_up_pos.r_right,RN_DIR_UP)
    #return astar_pathfind_betweenrooms(d,entity,from_node,stairs_down) + [lower_stairs_up] + astar_pathfind_betweenrooms(d,entity,lower_stairs_up,to_node)
  #elif from_node[0] > to_node[0]:
    ## need to go upstairs first
    #stairs_up_pos = d.l.levels[from_node[0]].stairs_up_pos
    #higher_stairs_down_pos = d.l.tile_at(stairs_up_pos).to_pos
    #stairs_up = (from_node[0].level,stairs_up_pos.r_down,stairs_up_pos.r_right,RN_DIR_UP)
    #higher_stairs_down = (higher_stairs_down_pos.level,higher_stairs_down_pos.r_down,higher_stairs_down_pos.r_right,RN_DIR_DOWN)
    #return astar_pathfind_betweenrooms(d,entity,from_node,stairs_up) + [higher_stairs_down] + astar_pathfind_betweenrooms(d,entity,higher_stairs_down,to_node)
  if from_node[0] <> to_node[0]:
    raise SystemError
  result = []
  room_info = {} # keyed by (level, r_down, r_right, dir), value is Astar_roomnode
  room_info[from_node] = Astar_roomnode([],0)
  open_nodes = [] # heapq of Roomnode_to_process
  _heapq.heappush(open_nodes, Roomnode_to_process(0,straight_line_long_distance(from_node,to_node),from_node))
  destination_reached = 0
  while (not destination_reached and not len(open_nodes)==0):
    next_node = _heapq.heappop(open_nodes)
    room_network_thisroom = d.room_network.get_node(d,(next_node.level,next_node.r_down,next_node.r_right))
    for dir in (DIR_DOWN, DIR_UP, DIR_RIGHT, DIR_LEFT):
      if dir==next_node.dir:
        if not (dir in room_network_thisroom.exits_to_node.keys()):
          continue
        try_node = room_network_thisroom.exits_to_node[next_node.dir]
        portal_step = 1
      else:
        if room_network_thisroom.exits.get(dir,0):
          try_node = (next_node.level,next_node.r_down,next_node.r_right,dir)
          portal_step = 0
        else:
          try_node = None
      if try_node==None:
        continue
      if portal_step==1:
        steps = 1
      else:
        if entity.info().can_swim:
          if next_node.dir not in room_network_thisroom.water_routes:
            continue
          elif dir not in room_network_thisroom.water_routes[next_node.dir]:
            continue
          steps = room_network_thisroom.water_routes[next_node.dir][dir]       
        else:
          if next_node.dir not in room_network_thisroom.routes:
            continue
          elif dir not in room_network_thisroom.routes[next_node.dir]:
            continue
          steps = room_network_thisroom.routes[next_node.dir][dir]
          if steps is None:
            continue # there is a wet route, but not a dry one
      add = 0
      if try_node in room_info:
        if next_node.moves_to + steps < room_info[try_node].moves_to:
          add = 1          
      else:
        add = 1
      if add:
        path1 = room_info[(next_node.level,next_node.r_down,next_node.r_right,next_node.dir)].path_to
        if path1 is None:
          print "aa"
          if not entity.is_character:
            print entity.type
          print entity.pos
        if next_node.moves_to is None:
          print "ab"
          if not entity.is_character:
            print entity.type
          print entity.pos
        if steps is None:
          print "ac"
          if not entity.is_character:
            print entity.type
          print entity.pos        
        room_info[try_node] = Astar_roomnode(path1+[try_node],next_node.moves_to+steps)
        _heapq.heappush(open_nodes, Roomnode_to_process(next_node.moves_to+steps,straight_line_long_distance(try_node,to_node),try_node))
        if try_node[0] == to_node[0] and try_node[1] == to_node[1] and try_node[2] == to_node[2] and try_node[3] == to_node[3]:
          destination_reached = 1
          break
  if not destination_reached:
      return None
  else:
      return room_info[to_node].path_to
    
def long_pathfind(d,entity,from_pos,to_pos,exclude_near_from_pos,max_moves_if_in_same_room=1e6):
  # obstacles in the current room should be in exclude_near_from_pos, a [Pos]
  # If no path, return None
  # If a path that does not leave the room, return it as a [[Pos]] not including from_pos
  # Else return a 3-tuple - a [(down,right)] leading from (and not including) from_pos to a nearby exit, then a [(level,r_down,r_right,dir)] to get to an exit in the same room as to_pos, then a [(down,right)] to walk to to_pos (again not including the first step).
  #  CHANGED - Now return the above 3-tuple, AND a flag which is 1 if any of the exclusions bit. 
  # Characters get restricted info about waypoints.
  #
  # print "navigate from ",str(from_pos)," to ",str(to_pos)
  obstruction = 0
  if from_pos.same_room(to_pos):
    # print entity.name," trying to long_pathfind (1) from ",from_pos," to ",to_pos," - calling astar_pathfind_within_room since same room"
    result,obstruction = astar_pathfind_withinroom(d,from_pos,to_pos,exclude_near_from_pos,entity.info().can_swim,max_range=max_moves_if_in_same_room) 
    return [result],obstruction
  elif from_pos.level < to_pos.level:
    # need to go downstairs first
    found_path = 0
    best_path_length = 1e6
    best_path = None
    for stairs_down_pos in d.l.levels[from_pos.level].stairs_down_pos:
      lower_stairs_up_pos = d.l.tile_at(stairs_down_pos).to_pos
      if 20*(abs(from_pos.r_down - stairs_down_pos.r_down)+abs(from_pos.r_right - stairs_down_pos.r_right)) > best_path_length:
        continue
      #print entity.name," recursively calling long_pathfind, to get from ",from_pos," to stairs at ",stairs_down_pos
      path1,this_obstruction = long_pathfind(d,entity,from_pos,stairs_down_pos,exclude_near_from_pos)
      if path1 is None or path1[0] is None:
        continue
      if len(path1)==1:
        path1 = [path1[0],[],[]]
      if len(path1[0])+20*len(path1[1])>best_path_length:
        continue
      #print entity.name," recursively calling long_pathfind, to get from stairs at ",lower_stairs_up_pos," to ",to_pos
      path2,junk = long_pathfind(d,entity,lower_stairs_up_pos,to_pos,[])
      if path2 is None:
        continue
      if len(path2)==1:
        path2 = [path2[0],[],[]]
      path_length = len(path1[0])+20*len(path1[1])+20*len(path2[1])+len(path2[2])
      if path_length < best_path_length:
        best_path_length = path_length
        best_path = path1[0],path1[1]+[(stairs_down_pos.level,stairs_down_pos.r_down,stairs_down_pos.r_right,RN_DIR_DOWN),(lower_stairs_up_pos.level,lower_stairs_up_pos.r_down,lower_stairs_up_pos.r_right,RN_DIR_UP)]+path2[1],path2[2]
        obstruction = this_obstruction
    if best_path is not None:
      return best_path,obstruction
    else:
      return None,0
  elif from_pos.level > to_pos.level:
    # need to go upstairs first
    found_path = 0
    best_path_length = 1e6
    best_path = None
    for stairs_up_pos in d.l.levels[from_pos.level].stairs_up_pos:
      higher_stairs_down_pos = d.l.tile_at(stairs_up_pos).to_pos
      if 20*(abs(from_pos.r_down - stairs_up_pos.r_down)+abs(from_pos.r_right - stairs_up_pos.r_right)) > best_path_length:
        continue
      #print entity.name," recursively calling long_pathfind, to get from ",from_pos," to stairs at ",stairs_up_pos
      path1,this_obstruction = long_pathfind(d,entity,from_pos,stairs_up_pos,exclude_near_from_pos)
      if path1 is None or path1[0] is None:
        continue
      if len(path1)==1:
        path1 = [path1[0],[],[]]
      if len(path1[0])+20*len(path1[1])>best_path_length:
        continue
      #print entity.name," recursively calling long_pathfind, to get from stairs at",higher_stairs_down_pos," to ",to_pos
      path2,junk = long_pathfind(d,entity,higher_stairs_down_pos,to_pos,[])
      if path2 is None:
        continue
      if len(path2)==1:
        path2 = [path2[0],[],[]]    
      path_length = len(path1[0])+20*len(path1[1])+20*len(path2[1])+len(path2[2])
      if path_length < best_path_length:
        best_path_length = path_length
        best_path = path1[0],path1[1]+[(stairs_up_pos.level,stairs_up_pos.r_down,stairs_up_pos.r_right,RN_DIR_UP),(higher_stairs_down_pos.level,higher_stairs_down_pos.r_down,higher_stairs_down_pos.r_right,RN_DIR_DOWN)]+path2[1],path2[2]
        obstruction = this_obstruction
    if best_path is not None:
      return best_path,obstruction
    else:
      return None,0
  from_network_node = d.room_network.get_node(d,(from_pos.level,from_pos.r_down,from_pos.r_right))
  if abs(from_pos.r_down-to_pos.r_down) + abs(from_pos.r_right-to_pos.r_right) == 1:
    # orthogonally adjacent rooms, try a shortcut?
    if from_pos.r_down > to_pos.r_down:
      dir_to_go = DIR_UP
    elif from_pos.r_right > to_pos.r_right:
      dir_to_go = DIR_LEFT
    elif from_pos.r_down < to_pos.r_down:
      dir_to_go = DIR_DOWN
    elif from_pos.r_right < to_pos.r_right:
      dir_to_go = DIR_RIGHT
    if from_network_node.exits.get(dir_to_go,0):
      #print entity.name," trying to long_pathfind (2) from ",from_pos," to ",to_pos," - calling astar_pathfind_within_room twice since orthogonally adjacent rooms"
      path1,obstruction = astar_pathfind_withinroom(d,from_pos,from_network_node.exits_pos[dir_to_go],exclude_near_from_pos,entity.info().can_swim)
      if path1 is not None:
        path2,junk = astar_pathfind_withinroom(d,from_network_node.exits_to[dir_to_go],to_pos,[],entity.info().can_swim)
        if path2 is not None:
          best_path = (path1, [(from_pos.level,from_pos.r_down,from_pos.r_right,dir_to_go),(to_pos.level,to_pos.r_down,to_pos.r_right,opposite(dir_to_go))], path2)
          return best_path, obstruction
  dirs_near_from_pos = {} # key is dir, value is moves to get there
  paths_to_dirs_near_from_pos = {} # key is dir, value is path to get there
  obstructions_to_dirs_near_from_pos = {} # key is dir, value is switch
  for dir in (DIR_DOWN, DIR_UP, DIR_RIGHT, DIR_LEFT):
    if from_network_node.exits.get(dir,0):
      #print entity.name," trying to long_pathfind (3) from ",from_pos," to ",to_pos," - first step is to call astar_pathfind_within_room to get to ",from_network_node.exits_pos[dir]
      path,obstruction = astar_pathfind_withinroom(d,from_pos,from_network_node.exits_pos[dir],exclude_near_from_pos,entity.info().can_swim)
      if path is not None:
        dirs_near_from_pos[dir] = len(path)      
        paths_to_dirs_near_from_pos[dir] = path
        obstructions_to_dirs_near_from_pos[dir] = obstruction
  dirs_near_to_pos = {} # key is dir, value is moves to get there
  paths_to_dirs_near_to_pos = {} # key is dir, value is path to get there
  to_network_node = d.room_network.get_node(d,(to_pos.level,to_pos.r_down,to_pos.r_right))
  for dir in (DIR_DOWN, DIR_UP, DIR_RIGHT, DIR_LEFT):
    if to_network_node.exits.get(dir,0):
      #print entity.name," trying to long_pathfind (4) from ",from_pos," to ",to_pos," - last step is to call astar_pathfind_within_room to get from ",to_network_node.exits_pos[dir]
      path,junk = astar_pathfind_withinroom(d,to_network_node.exits_pos[dir],to_pos,[],entity.info().can_swim)
      if path is not None:
        dirs_near_to_pos[dir] = len(path)
        paths_to_dirs_near_to_pos[dir] = path
  min_length = 1e6
  min_length_at_from_dir = None
  min_length_at_to_dir = None
  best_path = []
  for from_dir in dirs_near_from_pos:
    for to_dir in dirs_near_to_pos:
      path = astar_pathfind_betweenrooms(d,entity,(from_pos.level,from_pos.r_down,from_pos.r_right,from_dir),(to_pos.level,to_pos.r_down,to_pos.r_right,to_dir))
      if path is not None:
        if len(path) < min_length:
          min_length = len(path)
          best_path = path
          min_length_at_from_dir = from_dir
          min_length_at_to_dir = to_dir
  if min_length==1e6:
    return None,0
  best_path = (paths_to_dirs_near_from_pos[min_length_at_from_dir],[(from_pos.level,from_pos.r_down,from_pos.r_right,min_length_at_from_dir)]+best_path,paths_to_dirs_near_to_pos[min_length_at_to_dir])
  return best_path,obstructions_to_dirs_near_from_pos[min_length_at_from_dir]

def path_arduousness(result_of_long_pathfind):
  if result_of_long_pathfind is None or (len(result_of_long_pathfind)==1 and result_of_long_pathfind[0] is None):
    return 1e6
  elif len(result_of_long_pathfind)==1:
    return len(result_of_long_pathfind[0])
  elif result_of_long_pathfind[0] is None:
    return len(result_of_long_pathfind[2]) + 10*len(result_of_long_pathfind[1])
  elif result_of_long_pathfind[2] is None:
    return len(result_of_long_pathfind[0]) + 10*len(result_of_long_pathfind[1])
  else:
    return len(result_of_long_pathfind[0]) + len(result_of_long_pathfind[2]) + 10*len(result_of_long_pathfind[1])
  
class Path: # EXTERIOR USE
  source = None # Pos
  destination = None # Pos
  first_steps = [] # [Pos] - if this is None then the path needs to be recalculated
  second_nodes = None # or [(level,r_down,r_right,dir)]
  third_steps = None # or [Pos]
  # To get from source to destination, the next thing you need to do is to step along first_steps (which won't include your current loc), then traverse second_nodes, then third_steps
  actual_destination = None # Pos - where you're actually going - may not be the same as destination, the end of the path
  last_step = None # a Pos - if an entity gets pushed, current_pos may no longer be the same as this - then recalc
  
  def __init__(self,d,current_pos,destination,exclude,mild_exclude,entity):
    self.actual_destination = destination.copy()
    self.source = current_pos.copy()
    self.last_step = self.source.copy()
    self.entity = entity
    #print "path being created for ",entity.name," from ",current_pos," to ",destination
    self.recalc_path(d,current_pos.copy(),exclude,mild_exclude)
               
  def pop_next_step(self,d,current_pos,exclude,mild_exclude):
    # return a Pos - if no move, then return current_pos
    # update the path
    if self.first_steps is None or self.last_step<>current_pos or random.random()<0.2:
      self.last_step = current_pos.copy()
      #print "popping next step (1) for ",self.entity.name," at ",current_pos
      if self.recalc_path(d,current_pos,exclude,mild_exclude):
        return self.pop_next_step(d,current_pos,exclude,mild_exclude)
      else:
        return None
    if len(self.first_steps)>0:
      step = self.first_steps[0].copy() 
      self.last_step = step.copy()
      self.first_steps = self.first_steps[1:]
    elif d.l.tile_at(current_pos).info().is_portal:
      self.last_step = d.l.tile_at(current_pos).to_pos.copy()
      step = d.l.tile_at(current_pos).to_pos.copy()
      self.first_steps = None
    else:
      return current_pos
    if step in exclude:
      self.last_step = current_pos.copy()
      #print "popping next step (2) for ",self.entity.name," at ",current_pos
      if self.recalc_path(d,current_pos,exclude,mild_exclude):
        return self.pop_next_step(d,current_pos,exclude,mild_exclude)
      else:
        return current_pos   
    elif step in mild_exclude:
      return current_pos
    return step
   
  def recalc_path(self,d,current_pos,exclude,mild_exclude):
    # return 1 if a new path found, 0 else
    self.destination = self.actual_destination
    if len(mild_exclude)>0:
      #print self.entity.name," calling long_pathfind to do recalc_path from ",current_pos," to ",self.destination
      path1,obstruction = long_pathfind(d,self.entity,current_pos,self.destination,exclude)
      if path1 is None:
        path = path1
      else:
        mildly_excluded = 0
        if path1[0] is not None:
          for down_right in path1[0][0:min(10,len(path1[0]))]:
            pos = Pos(current_pos.level,current_pos.r_down,current_pos.r_right,down_right[0],down_right[1])
            if pos in mild_exclude:
              mildly_excluded = 1
        if not mildly_excluded:
          path = path1
        else:
          # print self.entity.name," trying again with different exclusions"
          path2,obstruction = long_pathfind(d,self.entity,current_pos,self.destination,exclude+mild_exclude,max_moves_if_in_same_room=min(10,2*path_arduousness(path1)))
          if path2 is None or path_arduousness(path1) < 1.5*path_arduousness(path2):
            path = path1
          else:
            path = path2
    else:
      #print self.entity.name," calling long_pathfind to do recalc_path from ",current_pos," to ",self.destination," with no exclusions"
      path,junk = long_pathfind(d,self.entity,current_pos,self.destination,exclude)
    if path is not None:
      if len(path)==3:
        self.first_steps = []
        if path[0] is None:
          self.first_steps = None
          return 0
        for step in path[0]:
          self.first_steps.append(Pos(current_pos.level,current_pos.r_down,current_pos.r_right,step[0],step[1]))
        self.second_nodes = path[1]
        self.third_steps = []
        for step in path[2]:
          self.third_steps.append(Pos(current_pos.level,current_pos.r_down,current_pos.r_right,step[0],step[1])) 
      elif len(path)==1:
        self.first_steps = []
        if path[0] is None:
          self.first_steps = None
          return 0
        for step in path[0]:
          self.first_steps.append(Pos(current_pos.level,current_pos.r_down,current_pos.r_right,step[0],step[1]))
        self.second_nodes = None
        self.third_steps = None
      return 1
    else:
      return 0
    
  def change_destination(self,d,current_pos,new_destination):
    # we are aiming for a different spot - we may throw away the path and start again, if in doubt
    self.actual_destination = new_destination.copy()
    if current_pos.same_room(self.actual_destination):
      self.first_steps = None
    elif not self.destination.same_room(self.actual_destination):
      self.first_steps = None
    elif self.destination.same_room(current_pos):
      if min(current_pos.distance_within_room(new_destination),len(self.first_steps)) < 3*self.destination.distance_within_room(new_destination):
        self.first_steps = None
      
def go_for_nearby_exit(d,entity,current_pos,exits_ok,monster_exits_ok,exclude,mild_exclude,dont_use_dirs): # EXTERIOR USE
  # return a Path object if a path to a nearby exit could be found or None else
  # exits_ok and monster_exits_ok are boolean flags indicating what kind of exits can be used
  # dont_use_dirs is a [DIR_] or None
  # exclude is a [pos] or None
  this_room = d.l.room_at(current_pos)
  exit_locs = []
  preferred_exit_locs = []
  if this_room.exit_pos is not None and exits_ok and not (this_room.exit_pos in exclude):
    exit_locs.append(this_room.exit_pos)
    preferred_exit_locs.append(this_room.exit_pos)
  if this_room.monster_exit_pos is not None and monster_exits_ok and not (this_room.monster_exit_pos in exclude):
    exit_locs.append(this_room.monster_exit_pos)
    preferred_exit_locs.append(this_room.monster_exit_pos)
  for dir in [DIR_UP,DIR_DOWN,DIR_LEFT,DIR_RIGHT]:
    if dont_use_dirs is None or not dir in dont_use_dirs:
      door_pos = this_room.get_mid_wall(dir)
      if door_pos in this_room.doors_pos and not (door_pos in exclude) and d.l.tile_at(door_pos).info().walkable(entity):
        exit_locs.append(door_pos)
  if this_room.stairs_up_pos is not None and not DIR_UP in dont_use_dirs and not (this_room.stairs_up_pos in exclude):
    exit_locs.append(this_room.stairs_up_pos)
  if this_room.stairs_down_pos is not None and not DIR_DOWN in dont_use_dirs and not (this_room.stairs_down_pos in exclude):
    exit_locs.append(this_room.stairs_down_pos)
  best_length = 1e6
  best_dest = None
  for pos in exit_locs:
    if pos in exclude:
      continue
    #print entity.name," trying to escape from ",current_pos," to ",pos," using astar_pathfind_within_room"
    short_path,junk = astar_pathfind_withinroom(d,current_pos.copy(),pos,exclude,entity.info().can_swim)
    if short_path is not None:
      if len(short_path) < best_length:
        best_dest = pos
        best_length = len(short_path)
      elif pos in preferred_exit_locs and len(short_path)/3.0 < best_length:
        best_dest = pos
        best_length = len(short_path)/3.0
  if best_dest is None:
    return None
  else:
    return Path(d,current_pos.copy(),best_dest,exclude,mild_exclude,entity)
      
def step_with_regard_to(d,me,exclude,pos_to_approach,pos_to_escape):  # EXTERIOR USE
  # return a Pos or none
  # 'me' is an entity, all the subsequent arguments are [Pos] or None (All pos's should be in the same room!!)
  # Not suitable for pathfinding - only for getting further away from nearby enemies (possibly moving towards nearby exits), 
  # or for moving towards an enemy in open space...
  this_pos = me.pos.copy()
  room = d.l.room_at(this_pos)
  tile = room.tiles[this_pos.down][this_pos.right]
  if pos_to_escape is not None:
    # leave the room if possible
    if tile.info().is_portal:
      return tile.to_pos
    elif me.is_character and tile.info().is_exit:
      return None      
    elif not me.is_character and tile.info().is_monster_exit:
      return None     
  options = [this_pos.copy()]
  option_preferences = {} # key is (down,right) from options, value is preference  
  option_preferences[(this_pos.down,this_pos.right)] = 0.0
  for down_right in d.shells[1]:
    this_pos.down = me.pos.down + down_right[0]
    this_pos.right = me.pos.right + down_right[1]   
    if d.l.valid(this_pos):
      if not this_pos in exclude:
        if room.tiles[this_pos.down][this_pos.right].info().walkable(me):
          options.append(this_pos.copy())
          option_preferences[(this_pos.down,this_pos.right)] = 0.0
  for option_pos in options:
    preference = option_preferences[(option_pos.down,option_pos.right)]
    if pos_to_approach is not None:
      for this_pos_to_approach in pos_to_approach:
        if this_pos_to_approach.same_room(me.pos):
          preference = preference - 0.8*option_pos.distance_within_room(this_pos_to_approach)
    if pos_to_escape is not None:
      for this_pos_to_escape in pos_to_escape:
        if this_pos_to_escape.same_room(me.pos):
          preference = preference + option_pos.distance_within_room(this_pos_to_escape)    
    option_preferences[(option_pos.down,option_pos.right)] = preference  
  max_preference = -1.0e6
  max_preference_at = None
  for option_pos in options:
    if option_preferences[(option_pos.down,option_pos.right)] > max_preference:
      max_preference_at = option_pos
      max_preference = option_preferences[(option_pos.down,option_pos.right)]
  return max_preference_at # Later, allow it to use exits/doors

def path_available_for_key_placement(d,from_pos,to_pos,exclude_exits):
  # exclude_posses should be a [(level,r_i,r_j,dir)]
  # return 0 or 1
  if from_pos.same_room(to_pos):
    return 1
  elif from_pos.level < to_pos.level:
    # need to go downstairs first
    for stairs_down_pos in d.l.levels[from_pos.level].stairs_down_pos:     
      lower_stairs_up_pos = d.l.tile_at(stairs_down_pos).to_pos
      # print "can we do it by going via stairs down at ",stairs_down_pos,"?"
      if path_available_for_key_placement(d,from_pos,stairs_down_pos,exclude_exits) and path_available_for_key_placement(d,lower_stairs_up_pos,to_pos,exclude_exits):
        ok = 0
        for dir in [DIR_RIGHT,DIR_LEFT,DIR_UP,DIR_DOWN]:
          if not ((lower_stairs_up_pos.level,lower_stairs_up_pos.r_down,lower_stairs_up_pos.r_right,dir) in exclude_exits):
            ok = 1
        if ok:
          # print "yes"
          return 1
        else:
          pass
          # print "no"          
      else:
        pass
        # print "no"
    # print "give up"
    return 0
  elif from_pos.level > to_pos.level:
    for stairs_up_pos in d.l.levels[from_pos.level].stairs_up_pos:
      # print "can we do it by going via stairs down at ",stairs_up_pos,"?"
      higher_stairs_down_pos = d.l.tile_at(stairs_up_pos).to_pos
      if path_available_for_key_placement(d,from_pos,stairs_up_pos,exclude_exits) and path_available_for_key_placement(d,higher_stairs_down_pos,to_pos,exclude_exits):
        ok = 0
        for dir in [DIR_RIGHT,DIR_LEFT,DIR_UP,DIR_DOWN]:
          if not ((higher_stairs_down_pos.level,higher_stairs_down_pos.r_down,higher_stairs_down_pos.r_right,dir) in exclude_exits):
            ok = 1
        if ok:
          # print "yes"
          return 1
        else:
          pass
          # print "no" 
      else:
        pass
        # print "no"
    # print "give up"
    return 0
  from_network_node = d.room_network_for_keys.get_node(d,(from_pos.level,from_pos.r_down,from_pos.r_right))
  dirs_near_from_pos = {} # key is dir, value is moves to get there
  for dir in (DIR_DOWN, DIR_UP, DIR_RIGHT, DIR_LEFT):
    if from_network_node.exits.get(dir,0):
      if not ((from_pos.level,from_pos.r_down,from_pos.r_right,dir) in exclude_exits):
        path,obstruction = astar_pathfind_withinroom(d,from_pos,from_network_node.exits_pos[dir],[],0)
        if path is not None:
          dirs_near_from_pos[dir] = len(path)      
  dirs_near_to_pos = {} # key is dir, value is moves to get there
  to_network_node = d.room_network_for_keys.get_node(d,(to_pos.level,to_pos.r_down,to_pos.r_right))
  for dir in (DIR_DOWN, DIR_UP, DIR_RIGHT, DIR_LEFT):
    if to_network_node.exits.get(dir,0):
      if not ((to_pos.level,to_pos.r_down,to_pos.r_right,dir) in exclude_exits):
        path,junk = astar_pathfind_withinroom(d,to_network_node.exits_pos[dir],to_pos,[],0)
        if path is not None:
          dirs_near_to_pos[dir] = len(path)
  # print "dirs_near_from_pos = ",dirs_near_from_pos.keys()," and dirs_near_to_pos = ",dirs_near_to_pos.keys()
  for from_dir in dirs_near_from_pos:
    for to_dir in dirs_near_to_pos:
      # print "can we do it by going via dir ",from_dir," of ",from_pos," and dir ",to_dir," of ",to_pos,"?"
      path = astar_pathfind_betweenrooms_for_key_placement(d,(from_pos.level,from_pos.r_down,from_pos.r_right,from_dir),(to_pos.level,to_pos.r_down,to_pos.r_right,to_dir),exclude_exits)
      if path is not None:
        # print "yes we can"
        return 1
      else:
        pass
        # print "no we can't"
  return 0

def astar_pathfind_betweenrooms_for_key_placement(d,from_node,to_node,exclude_exits):
  # from_node and to_node should each be (level,r_i,r_j,dir) - on the same level but not in the same room
  # exclude_posses should be a [(level,r_i,r_j,dir)]
  # return 0 or 1
  result = []
  room_info = {} # keyed by (level, r_down, r_right, dir), value is Astar_roomnode
  room_info[from_node] = Astar_roomnode([],0)
  open_nodes = [] # heapq of Roomnode_to_process
  _heapq.heappush(open_nodes, Roomnode_to_process(0,straight_line_long_distance(from_node,to_node),from_node))
  destination_reached = 0
  while (not destination_reached and not len(open_nodes)==0):
    next_node = _heapq.heappop(open_nodes)
    room_network_thisroom = d.room_network_for_keys.get_node(d,(next_node.level,next_node.r_down,next_node.r_right))
    for dir in (DIR_DOWN, DIR_UP, DIR_RIGHT, DIR_LEFT):
      if dir==next_node.dir:
        if not (dir in room_network_thisroom.exits_to_node.keys()):
          continue
        try_node = room_network_thisroom.exits_to_node[next_node.dir]
        portal_step = 1
      else:
        if room_network_thisroom.exits.get(dir,0):
          try_node = (next_node.level,next_node.r_down,next_node.r_right,dir)
          portal_step = 0
        else:
          try_node = None
      if try_node==None:
        continue
      if try_node in exclude_exits:
        continue
      if portal_step==1:
        steps = 1
      else:
        if next_node.dir not in room_network_thisroom.routes:
          continue
        elif dir not in room_network_thisroom.routes[next_node.dir]:
          continue
        steps = room_network_thisroom.routes[next_node.dir][dir]
        if steps is None:
          continue # there is no route
      add = 0
      if try_node in room_info:
        if next_node.moves_to + steps < room_info[try_node].moves_to:
          add = 1          
      else:
        add = 1
      if add:
        room_info[try_node] = Astar_roomnode(room_info[(next_node.level,next_node.r_down,next_node.r_right,next_node.dir)].path_to+[try_node],next_node.moves_to+steps)
        _heapq.heappush(open_nodes, Roomnode_to_process(next_node.moves_to+steps,straight_line_long_distance(try_node,to_node),try_node))
        if try_node[0] == to_node[0] and try_node[1] == to_node[1] and try_node[2] == to_node[2] and try_node[3] == to_node[3]:
          return 1
  return 0

# do some psyco bindings 
psyco.bind(Astar_node.__init__)
psyco.bind(astar_pathfind_withinroom)
psyco.bind(astar_pathfind_betweenrooms)
psyco.bind(long_pathfind)
psyco.bind(Node_to_process.__cmp__)
psyco.bind(Node_to_process.__init__)
psyco.bind(step_with_regard_to)
psyco.bind(go_for_nearby_exit)
